\chapter{Úvod}

Dilatácia grafu -- problém, ktorý z algoritmického hľadiska patrí do úloh kategórie NP-úplnych problémov. Vybrali sme si tento problém, pretože je ako stvorený pre výpočet na distribuovanom počítači za cieľom urýchlenia výpočtu.

Našou úlohou bude teda implementovať program, ktorý bude riešiť dilatáciu grafu jednak sekvenčne a jednak paralelne.

Po danej impelementácii a vyriešení implementačných podúloh budeme program testovať na viacerých vstupoch, s rôznymi parametrami a na rôznom počte procesorov. Tým by sme si mali potvrdiť náš odhad zrýchlenia.


\section{Zadanie úlohy}

\begin{description}
\item[Vstupné dáta] \hfill
\begin{description}
\item Nech $G(V,E)$ je jednoduchý neorientovaný neohodnotený súvislý graf o $n$ uzloch, $m$ hranách a priemerným stupňom uzla $k$. 
\item Prirodzené číslo $n$ je číslo predstavujúce počet uzlov grafu $G$, kde $n \ge 5$.
\item A prirodzené číslo $k$ znamená priemerný stupeň uzla grafu $G$ tak, že platí $n > k \ge 3$
\end{description}
\item[Definície] \hfill 

Predpokladajme, že uzly grafu $G$ sú očíslované číslami od $1,\ldots, n$. Nech $p_{i}$ je ľubovoľná permutácia množiny $\left\lbrace1, \ldots ,n\right\rbrace$ a $p_{i}\left(G\right)$ je graf $G$ vnorený do celočíselnej osy $1, \ldots ,n$ v poradí permutácie $p_{i}$. 
\begin{description} 
\item Potom \textit{dilatácia hrany} je vzdialenosť koncových uzlov hrany na celočíslnej osy vnorenia $p_{i}\left(G\right)$.
\item \textit{Dilatácia permutácie} $p_{i}$ je maximálna dilatácia z množiny dilatácií všetkých hrán.
\item \textit{Dilatáciu grafu} $G$ definujeme ako minimálnu dilatáciu z množiny dilatácií všetkých permutácií. 
\end{description}
\item[Úloha a výstup] \hfill

Úlohou bude nájdenie dilatácie grafu a teda nájdenie hodnoty dilatácie grafu $G$ s odpovedajúcou permutáciou $p_{i}$.

Riešenie danej úlohy bude existovať vždy, nemusí byť jednoznačné. Existuje dolná tesná hranica hodnoty výslednej dilatácie grafu $G$ rovnajúca sa 
\begin{equation} 
\ceil{\frac{n - 1}{\o\left(G\right)}}
\end{equation}
\end{description}